---
id: 5900f49f1000cf542c50ffb1
title: 'Завдання 306: гра з паперовими смужками'
challengeType: 1
forumTopicId: 301960
dashedName: problem-306-paper-strip-game
---

# --description--

Наведена нижче гра є класичним прикладом комбінаторної теорії ігор:

Двоє гравців починають зі смужки з $n$ білих квадратів і ходять по черзі. Під час кожного ходу гравець вибирає два суміжних білих квадрати і розмальовує їх у чорний колір. Програє той гравець, який не може зробити хід.

- $n = 1$: немає дійсних ходів, тому перший гравець автоматично програє.
- $n = 2$: лише один дійсний хід, після якого другий гравець програє.
- $n = 3$: два дійсні ходи, але в обох програє другий гравець.
- $n = 4$: три дійсні ходи для першого гравця, який може виграти гру, замалювавши два середніх квадрати.
- $n = 5$: чотири дійсні ходи для першого гравця (показано нижче червоним кольором), але незважаючи на його дії, виграє другий гравець (синій колір).

<img class="img-responsive center-block" alt="дійсні початкові ходи на смужці з 5 квадратів" src="https://cdn.freecodecamp.org/curriculum/project-euler/paper-strip-game.gif" style="background-color: white; padding: 10px;" />

Тому за умови $1 ≤ n ≤ 5$ існує три значення $n$, за яких може виграти перший гравець.

Так само за умови $1 ≤ n ≤ 50$ існує сорок значень $n$, за яких може виграти перший гравець.

Скільки існує значень $n$ за умови $1 ≤ n ≤ 1\\,000\\,000$, за яких може виграти перший гравець?

# --hints--

`paperStripGame()` має повернути `852938`.

```js
assert.strictEqual(paperStripGame(), 852938);
```

# --seed--

## --seed-contents--

```js
function paperStripGame() {

  return true;
}

paperStripGame();
```

# --solutions--

```js
// solution required
```
